#include<vector>
#include<iostream>
using namespace std;
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for (auto e : nums)
            sum += e;
        if (sum % 2)
            return false;
        vector<bool> dp(sum / 2 + 1, false);
        dp[0] = true;

        for (int i = 1; i <= n; i++)
            for (int j = sum / 2; j >= nums[i - 1]; j--)
                dp[j] = dp[j] || dp[j - nums[i - 1]];

        return dp[sum / 2];
    }
};

int main() {
    vector<int> nums = { 1,2,3,5 };
    int n = nums.size();
    int sum = 0;
    for (auto e : nums)sum += e;
    vector<vector<bool>> dp(n + 1, vector<bool>(sum / 2 + 1, false));
    for (auto& e : dp)e[0] = true;
    for (auto e : dp) {
        for (auto t : e)cout << t << ' ';
        cout << endl;
    }
 
	return 0;
}